後置記法から前置記法への変換

目的

あなたの目標は、後置記法の式（逆ポーランド記法）を、その同等の前置記法の式（ポーランド記法）に変換することです。これは、式木を構築し、その木を走査することで実現します。

アルゴリズム

1. 式木の構築： スタックを用いて、後置記法の式を左から右へ順に処理します。
   • 演算子が見つかった場合、オペランド（例：A、B）を見つけると、それ自身をノードとする単一ノードの木を作成し、スタックにプッシュします。
   • 演算子が見つかった場合、演算子（例：+、*）が見つかると、スタックから2つの木をポップします。最初にポップしたものが右側の子（T₂）で、2番目にポップしたものが左側の子（T₁）となります。この演算子をルートとする新しい木を作成し、スタックに戻します。
2. 前置記法の文字列の生成：すべてのトークンを処理した後、スタックには完成した式木が残っています。この木に対して前順走査（ルート → 左 → 右）を実行して、最終的な前置記法の式を生成します。

例

後置記法の式A B + C *に対して、アルゴリズムは以下の木を構築します：

  *
   / \
  +   C
 / \
A   B

前順走査により得られる前置記法の式は：* + A B C。

入出力形式

入力

• 行1：整数N（1 ≤ N≤ 1000）、トークンの個数。
• 行2：後置記法の式。トークンはNスペースで区切られた

トークンの規則

• オペランド：大文字の1文字（A–Z）
• 演算子：4種類の二項演算子：+、–、*、/。

出力

• 対応する前置記法の式を、トークンをスペースで区切って1行に出力してください。

サンプル

サンプル1：

5

A B + C *

* + A B C

サンプル2：

7

A B C * + D /

/ + A * B C D

サンプル3：

7

A B + C D - *

* + A B - C D

制限事項